import java.util.LinkedList;
import java.util.Random;

public class Logic {
	
	// depth to do branching till
	private static final int DEPTH = 3;
	
	public static Node decidePath(Gamestate gamestate) throws Exception{
		Node root = new Node(gamestate);
		root.setDepth(0);
		
		/*
		 * Depth First Search Solution (Can implement with alpha-beta pruning)
		 */
		// this creates the branches which will be pruned at the same time.
		alphabeta(root, Integer.MIN_VALUE, Integer.MAX_VALUE, root.getGamestate().currentPlayer);
		getBestMove(root, root.getGamestate().currentPlayer);
		
		return root;
	}
	
	public static int alphabeta(Node n, int alpha, int beta, Gamestate.Player p) throws Exception {
		if (n.getDepth() == DEPTH) {
			return n.getHeuristic(p);
		} else if (n.getGamestate().currentPlayer == p) {
			LinkedList<Node> branches = getBranches(n);
			for (Node i : branches) {
				n.addBranch(i);
				i.setDepth(n.getDepth() + 1);
				alpha = Math.max(alpha, alphabeta(i, alpha, beta, p));
				if (beta <= alpha) {
					return alpha;
				}
			}
			return alpha;
		} else {
			LinkedList<Node> branches = getBranches(n);
			for (Node i : branches) {
				n.addBranch(i);
				i.setDepth(n.getDepth()+1);
				beta = Math.min(beta, alphabeta(i, alpha, beta, p));
				if (beta <= alpha) {
					return beta;
				}
			}
			return beta;
		}
	}

	public static void getBestMove(Node node, Gamestate.Player p) throws Exception{
		
		if (node.getDepth() == DEPTH) {
			node.setValueAssigned(node.getHeuristic(p));
		} else if (node.getGamestate().currentPlayer == p) {
			// choose maximum
			int max = Integer.MIN_VALUE;
			for (Node i : node.getBranches()) {
				Logic.getBestMove(i,p);
				int current = i.getValueAssigned();
				if (current > max) {
					max = current;
					node.setBestMove(i);
				}
			}
			node.setValueAssigned(max);
			
		} else {
			// choose minimum
			int min = Integer.MAX_VALUE;
			for (Node i : node.getBranches()) {
				Logic.getBestMove(i,p);
				int current = i.getValueAssigned();
				if (current < min) {
					min = current;
					node.setBestMove(i);
				}
			}
			node.setValueAssigned(min);
		}
	}
	
	private static LinkedList<Node> getBranches(Node current) throws Exception {
		// do branching on a node and return a LinkedList back
		LinkedList<Node> branches = new LinkedList<Node>();
		
		Boolean[][] possibleMoves = new Boolean[Gamestate.BOARD_SIZE][Gamestate.BOARD_SIZE];
		
		// If there exists an immediate way of winning, we win.
		Boolean win = false;
		for (WinningCombination w : current.getGamestate().winningCombinations.get(current.getGamestate().currentPlayer.ordinal())) {
			if (w.hasFour()) {
				for (int i = 0; i < 5; i++) {
					if (w.exists[i] == null || w.exists[i] == false) {
						switch (w.type) {
							case HORIZONTAL:
								possibleMoves[w.positionX+i][w.positionY] = true;
								win = true;
								break;
							case VERTICAL:
								possibleMoves[w.positionX][w.positionY+i] = true;
								win = true;
								break;
							case DIAGONALUP:
								possibleMoves[w.positionX+i][w.positionY-i] = true;
								win = true;
								break;
							case DIAGONALDOWN:
								possibleMoves[w.positionX+i][w.positionY+i] = true;
								win = true;
								break;
						}
					}
				}
			}
		}
		
		if (win) {
			for (int i = 0; i < Gamestate.BOARD_SIZE; i++) {
				for (int j = 0; j < Gamestate.BOARD_SIZE; j++) {
					if (possibleMoves[i][j] != null && possibleMoves[i][j] == true) {
						Node newNode = new Node(current, i, j);
						branches.add(newNode);
					}
				}
			}
			return branches;
		}
			
		// Next, we look for threats. 
		Boolean threats = false;
		Gamestate.Player nextPlayer = current.getGamestate().getNextPlayer();
		for (WinningCombination w : current.getGamestate().winningCombinations.get(nextPlayer.ordinal())) {
			// always block threats which have four vertices filled
			if (w.hasFour()) {
				switch (w.type) {
					case HORIZONTAL:
						// find positions, and add them
						for (int i = 0; i < 5; i++) {
							if (w.exists[i] == null || w.exists[i] == false) {
								possibleMoves[w.positionX+i][w.positionY] = true;
								threats = true;
							}
						}
						break;
					case VERTICAL:
						for (int i = 0; i < 5; i++) {
							if (w.exists[i] == null || w.exists[i] == false) {
								possibleMoves[w.positionX][w.positionY+i] = true;
								threats = true;
							}
						}
						break;
					case DIAGONALUP:
						for (int i = 0; i < 5; i++) {
							if (w.exists[i] == null || w.exists[i] == false) {
								possibleMoves[w.positionX+i][w.positionY-i] = true;
								threats = true;
							}
						}
						break;
					case DIAGONALDOWN:
						for (int i = 0; i < 5; i++) {
							if (w.exists[i] == null || w.exists[i] == false) {
								possibleMoves[w.positionX+i][w.positionY+i] = true;
								threats = true;
							}
						}
						break;
					}
			} else if (w.hasThree()) {
				// check if open three and add if so, delay if not
				switch (w.type) {
					case HORIZONTAL:
						if (!((w.positionX  == 0 && w.exists[0] != null && w.exists[0] == true) ||
							(w.positionX + 5 == Gamestate.BOARD_SIZE && w.exists[4] != null && w.exists[4] == true))) {
							if (w.straightThree()) {
								if (w.exists[0] != null && w.exists[0] == true) {
									possibleMoves[w.positionX+3][w.positionY] = true;
									threats = true;
								} else if (w.exists[1] != null && w.exists[1] == true){
									possibleMoves[w.positionX][w.positionY] = true;
									possibleMoves[w.positionX+4][w.positionY] = true;
									threats = true;
								} else {
									possibleMoves[w.positionX+1][w.positionY] = true;
									threats = true;
								}
							} else {
								// find positions, and add them
								for (int i = 0; i < 5; i++) {
									if (w.exists[i] == null || w.exists[i] == false) {
										possibleMoves[w.positionX+i][w.positionY] = true;
										threats = true;
									}
								}
							}
						}
						break;
					case VERTICAL:
						if (!((w.positionY == 0 && w.exists[0] != null && w.exists[0] == true ) ||
							(w.positionY + 5 == Gamestate.BOARD_SIZE && w.exists[4] != null && w.exists[4] == true))){
							if (w.straightThree()) {
								if (w.exists[0] != null && w.exists[0] == true) {
									possibleMoves[w.positionX][w.positionY+3] = true;
									threats = true;
								} else if (w.exists[1] != null && w.exists[1] == true){
									possibleMoves[w.positionX][w.positionY] = true;
									possibleMoves[w.positionX][w.positionY+4] = true;
									threats = true;
								} else {
									possibleMoves[w.positionX][w.positionY+1] = true;
									threats = true;
								}
							} else {
								for (int i = 0; i < 5; i++) {
									if (w.exists[i] == null || w.exists[i] == false) {
										possibleMoves[w.positionX][w.positionY+i] = true;
										threats = true;
									}
								}
							}
						}
						break;
					case DIAGONALUP:
						if (!(((w.positionX == 0 || w.positionY == Gamestate.BOARD_SIZE - 1) && w.exists[0] != null && w.exists[0] == true) ||
								  ((w.positionY - 4 == 0 || w.positionX + 4 == Gamestate.BOARD_SIZE - 1) && w.exists[4] != null && w.exists[4] == true))) {
							if (w.straightThree()) {
								if (w.exists[0] != null && w.exists[0] == true) {
									possibleMoves[w.positionX+3][w.positionY-3] = true;
									threats = true;
								} else if (w.exists[1] != null && w.exists[1] == true){
									possibleMoves[w.positionX][w.positionY] = true;
									possibleMoves[w.positionX+4][w.positionY-4] = true;
									threats = true;
								} else {
									possibleMoves[w.positionX+1][w.positionY-1] = true;
									threats = true;
								}
							} else {
								for (int i = 0; i < 5; i++) {
									if (w.exists[i] == null || w.exists[i] == false) {
										possibleMoves[w.positionX+i][w.positionY-i] = true;
										threats = true;
									}
								}
							}
						}
						break;
					case DIAGONALDOWN:
						if (!(((w.positionX == 0 || w.positionY == 0) && w.exists[0] != null && w.exists[0] == true) ||
								  ((w.positionY + 4 == Gamestate.BOARD_SIZE - 1 || w.positionX + 4 == Gamestate.BOARD_SIZE - 1) && w.exists[4] != null && w.exists[4] == true))) {		
							if (w.straightThree()) {
								if (w.exists[0] != null && w.exists[0] == true) {
									possibleMoves[w.positionX+3][w.positionY+3] = true;
									threats = true;
								} else if (w.exists[1] != null && w.exists[1] == true){
									possibleMoves[w.positionX][w.positionY] = true;
									possibleMoves[w.positionX+4][w.positionY+4] = true;
									threats = true;
								} else {
									possibleMoves[w.positionX+1][w.positionY+1] = true;
									threats = true;
								}
							} else {
								for (int i = 0; i < 5; i++) {
									if (w.exists[i] == null || w.exists[i] == false) {
										possibleMoves[w.positionX+i][w.positionY+i] = true;
										threats = true;
									}
								}
							}
						}
						break;
				}
			}
		}
		
		
		// If there exists anything, we just return it
		if (threats == true) {
			for (int i = 0; i < Gamestate.BOARD_SIZE; i++) {
				for (int j = 0; j < Gamestate.BOARD_SIZE; j++) {
					if (possibleMoves[i][j] != null && possibleMoves[i][j] == true) {
						Node newNode = new Node(current, i, j);
						branches.add(newNode);
					}
				}
			}
			return branches;
		}
		
		// Secondly, we look for possible threats to build up
		Boolean buildup = false;
		for (WinningCombination w : current.getGamestate().winningCombinations.get(current.getGamestate().currentPlayer.ordinal())) {
			for (int i = 0; i < 5; i++) {
				if (w.exists[i] == null || w.exists[i] == false) {
					switch (w.type) {
						case HORIZONTAL:
							possibleMoves[w.positionX+i][w.positionY] = true;
							buildup = true;
							break;
						case VERTICAL:
							possibleMoves[w.positionX][w.positionY+i] = true;
							buildup = true;
							break;
						case DIAGONALUP:
							possibleMoves[w.positionX+i][w.positionY-i] = true;
							buildup = true;
							break;
						case DIAGONALDOWN:
							possibleMoves[w.positionX+i][w.positionY+i] = true;
							buildup = true;
							break;
					}
				}
			}
		}
				
		if (buildup) {
			for (int i = 0; i < Gamestate.BOARD_SIZE; i++) {
				for (int j = 0; j < Gamestate.BOARD_SIZE; j++) {
					if (possibleMoves[i][j] != null && possibleMoves[i][j] == true) {
						Node newNode = new Node(current, i, j);
						branches.add(newNode);
					}
				}
			}
			return branches;
		}
		
		// Otherwise, we look for random possible locations to put everything
		int i = Gamestate.BOARD_SIZE/2;
		int j = Gamestate.BOARD_SIZE/2;
		Random generator = new Random();
		while (current.getGamestate().Board[i][j] != null) {
			// Randomise i and j
			i = generator.nextInt(Gamestate.BOARD_SIZE);
			j = generator.nextInt(Gamestate.BOARD_SIZE);
		}
		Node newNode = new Node(current, i, j);
		branches.add(newNode);
		
		return branches;
	}
	
}
